# 最少的1(好题)
# 2025/3/3
"""题目解析
对于这个问题最简单的想法其实就是暴力。
从1开始枚举，遇到n的倍数就记录其1的个数，如果更小就更新答案。
这个显然是不行的，因为不知道到哪里才能结束。 当然大部分人的第一感觉应该是枚举n的倍数。
跟上面一样不知道到哪结束，并且从提交的结果看枚举到1百万倍只能过40%。

我们知道上面的方法不可行, 所以我们可以考虑将问题转化为一个模n的余数问题:
假设我们正在构造一个数，每一步可以在末尾添加0或1，同时更新当前数的余数（模n的结果）。
当余数为0时，说明我们找到了一个n的倍数。
那么我们的目标就非常明确了, 使用最小的代价(最少的1)来找到余数为0的数.

路径的构建:
每一步可以选择在末尾添加0或1：
添加0：新余数 = (当前余数 * 2) % n，1的个数不变。
添加1：新余数 = (当前余数 * 2 + 1) % n，1的个数加1。
这样，每一步相当于从一个节点转移到另一个节点。每一步的选择（添加0或1）看作图中的一条边。
目标是从初始状态(1, 1)（1的个数, 当前余数）出发，找到一条到目标状态(k, 0)的最短路径。其中k是1的最小个数。

"""

import heapq
from collections import deque

from leetcode import test_function as tf


def min_ones_in_multiple_wrong(n):
    """一个错误的方法
    实际上返回的是n中包含1的个数, 而不是n的倍数中最小包含1的个数
    因为它本质上使用过构建一个二叉树来遍历, 只要是n的倍数就返回其中1的个数, 那么一定是返回一个最小的n的倍数, 也就是n本身
    """
    # 处理特殊情况
    if n == 1 or n == 0:
        return n
    visited = set()
    heap = []
    heapq.heappush(heap, (1, 1))  # (current_one_count, current_remainder)
    visited.add(1)

    while heap:
        cnt, rem = heapq.heappop(heap)
        if rem == 0:
            return cnt
        # 通过在二进制的末尾增加0或1来生成下一个可能的余数
        nxt_rem0 = (rem * 2) % n
        if nxt_rem0 not in visited:
            visited.add(nxt_rem0)
            heapq.heappush(heap, (cnt, nxt_rem0))
        nxt_rem1 = (rem * 2 + 1) % n
        if nxt_rem1 not in visited:
            visited.add(nxt_rem1)
            heapq.heappush(heap, (cnt + 1, nxt_rem1))


def min_count_one(n):
    """最简单的dijkstra"""
    if n == 1 or n == 0:
        return n
    dist = [float('inf')] * n
    stack = [(1, 1)]  # (1的个数, 余数)

    while stack:
        cnt, rem = stack.pop()
        if cnt > dist[rem]:
            continue

        for i in [0, 1]:
            new_rem = (rem * 2 + i) % n
            new_cnt = cnt + i
            if new_cnt < dist[new_rem]:
                dist[new_rem] = new_cnt
                stack.append((new_cnt, new_rem))

    return dist[0]


def min_ones_in_multiple_dijkstra(n):
    """dijkstra + 优先队列的方法
    优先队列的作用是确保我们总是优先处理1的个数最少的状态，从而避免无效的搜索路径。
    如果我们不使用优先队列，而是简单地使用普通队列（如BFS），可能会先处理一些1的个数较多的状态。
    这些状态虽然最终也能到达余数为0，但它们并不是最优解，因为它们的1的个数比某些后续状态多。
    优先队列按1的个数从小到大排序，因此当我们第一次遇到余数为0的状态时，它的1的个数一定是最小的。
    此外, 通过优先队列，我们可以动态地剪枝掉一些次优的路径。
    例如，如果我们已经找到了一个余数为r且1的个数为k的状态，那么后续所有1的个数大于k的路径都可以被忽略。
    """

    if n == 1:
        return 1
    min_counts = [float('inf')] * n  # 记录各余数对应的最小1的个数
    heap = []
    heapq.heappush(heap, (1, 1))  # (1的个数, 当前余数)
    min_counts[1] = 1

    while heap:
        count, rem = heapq.heappop(heap)
        if count > min_counts[rem]:  # 剪枝, 若当前路径的1的个数不是最优，跳过
            continue
        if rem == 0:
            return count
        # 尝试在二进制末尾添加0或1
        for bit in [0, 1]:
            new_rem = (rem * 2 + bit) % n
            new_count = count + bit
            # 仅当新路径更优时更新
            if new_count < min_counts[new_rem]:
                min_counts[new_rem] = new_count
                heapq.heappush(heap, (new_count, new_rem))
    return -1  # 理论上不会执行


def min_ones_in_multiple_bfs(n):
    """双端队列 + bfs的算法
    画一个由二进制数字组成的二叉树
                      1
              10                 11
        100      101       110        111
    1000 1001 1010 1011 1100 1101  1110 1111
    """
    min_counts = [float("inf")] * n
    que = deque([(1, 1)])
    while que:
        count, rem = que.pop()
        if min_counts[rem] > count:
            min_counts[rem] = count
            if rem % 2 == 0:
                que.append((count + 1, (rem + 1) % n))
            que.append((count, (rem * 2) % n))
    return min_counts[0]


# 示例用法
if __name__ == '__main__':
    # n = int(input())
    # print(min_ones_in_multiple(n))
    # 当n=11时, bin(11) = 1011, bin(22) = 10110, bin(33) = 100001
    print(min_ones_in_multiple_dijkstra(11))  # 2
    print(min_ones_in_multiple_wrong(11))  # 3
    # l = sieve(10000)
    inp = [{"n": 7}, {"n": 11}, {"n": 9697}, {"n": 999983}, ]
    out = [3, 2, 2, 3]
    tf(min_ones_in_multiple_dijkstra, inp, out)
    tf(min_ones_in_multiple_bfs, inp, out)
